package cn.hughie.trie;

import java.io.*;
import java.util.ArrayList;
import java.util.List;


/**
 * DoubleArrayTrie在构建双数组的过程中也借助于一棵传统的Trie树，但这棵Trie树并没有被保存下来，
 * 如果要查找以prefix为前缀的所有词不适合用DoubleArrayTrie，应该用传统的Trie树。
 *
 * @author zhangchaoyang
 */
public class DoubleArrayTrie {


    private static class Node {
        int code;// 字符的unicode编码 、 子节点的code == 自己的字符编码+1
        int depth;// 在Trie树中的深度
        int left;// 代表节点在字典中范围的左边界
        int right;// 代表节点在字典中范围的右边界
    }


    private int[] check; // check负责检查各个字符串是否是从同一个状态转移而来，当check[i]为负值时，表示此状态为字符串的结束。
    private int[] base; // base负责记录状态，用于状态转移；

    private boolean[] used;
    private int size;
    private int allocSize; // base、check、used数组当前的长度
    private List<String> key; // 所有的词
    private int keySize; // 词数量
    private int[] length;
    private int[] value;
    private int progress;
    private int nextCheckPos;
    int error;
    List<String> keys;


    public DoubleArrayTrie() {
        check = null;
        base = null;
        used = null;
        size = 0;
        allocSize = 0;
        error = 0;
    }

    /**
     * 扩充base、check、used数组
     *
     * @param newSize 扩容后的数组长度
     * @return
     */
    private int resize(int newSize) {
        int[] base2 = new int[newSize];
        int[] check2 = new int[newSize];
        boolean[] used2 = new boolean[newSize];
        if (allocSize > 0) {
            System.arraycopy(base, 0, base2, 0, allocSize);// 如果allocSize超过了base2的长度，会抛出异常
            System.arraycopy(check, 0, check2, 0, allocSize);
            System.arraycopy(used, 0, used2, 0, allocSize);
        }

        base = base2;
        check = check2;
        used = used2;

        allocSize = newSize;
        return allocSize;
    }

    /**
     * 生成parent的子节点，并让siblings引用指向他们
     *
     * @param parent   父节点
     * @param siblings 儿子节点
     * @return 儿子节点的数量
     */
    private int fetch(Node parent, List<Node> siblings) {
        if (error < 0)
            return 0;

        int prev = 0;

        for (int i = parent.left; i < parent.right; i++) {
            // 词的长度 >= 父节点的深度 必须
            if ((length != null ? length[i] : key.get(i).length()) < parent.depth)
                continue;

            String tmp = key.get(i);

            int cur = 0;
            // 词的长度 > 父节点的深度 时
            if ((length != null ? length[i] : tmp.length()) != parent.depth)
                cur = (int) tmp.charAt(parent.depth) + 1;

            if (prev > cur) {
                error = -3;
                return 0;
            }

            // 子节点 or 结束节点
            if (cur != prev || siblings.isEmpty()) {
                Node tmpNode = new Node();
                tmpNode.depth = parent.depth + 1;
                tmpNode.code = cur;
                tmpNode.left = i;
                // 修改上一个兄弟节点的right
                if (!siblings.isEmpty())
                    siblings.get(siblings.size() - 1).right = i;
                siblings.add(tmpNode);
            }
            prev = cur;
        }

        if (!siblings.isEmpty())
            siblings.get(siblings.size() - 1).right = parent.right;

        return siblings.size();
    }

    /**
     * @param siblings
     * @return
     */
    private int insert(List<Node> siblings) {
        if (error < 0)
            return 0;

        int begin = 0; // 子节点开始的数组下标、试base[s]
        int pos = ((siblings.get(0).code + 1 > nextCheckPos) ? siblings.get(0).code + 1 : nextCheckPos) - 1;
        int nonzeroNum = 0; // 不为0的个数
        int first = 0; // 记录是否第一次

        if (allocSize <= pos)
            resize(pos + 1);

        // 容量要足，挑选可用的坑
        outer:
        while (true) {
            pos++;

            if (allocSize <= pos)
                resize(pos + 1);

            if (check[pos] != 0) {
                nonzeroNum++;
                continue;
            } else if (first == 0) {
                nextCheckPos = pos;
                first = 1;
            }

            begin = pos - siblings.get(0).code;
            if (allocSize <= (begin + siblings.get(siblings.size() - 1).code)) {
                // progress can be zero
                double l = (1.05 > 1.0 * keySize / (progress + 1)) ? 1.05 : 1.0 * keySize / (progress + 1);
                resize((int) (allocSize * l));
            }

            if (used[begin])
                continue;

            for (int i = 1; i < siblings.size(); i++)
                if (check[begin + siblings.get(i).code] != 0)
                    continue outer;

            break;
        }

        if (1.0 * nonzeroNum / (pos - nextCheckPos + 1) >= 0.95)
            nextCheckPos = pos;

        used[begin] = true;
        size = (size > begin + siblings.get(siblings.size() - 1).code + 1) ? size : begin + siblings.get(siblings.size() - 1).code + 1;

        for (int i = 0; i < siblings.size(); i++)
            check[begin + siblings.get(i).code] = begin;

        for (int i = 0; i < siblings.size(); i++) {
            List<Node> newSiblings = new ArrayList<>();

            if (fetch(siblings.get(i), newSiblings) == 0) {
                base[begin + siblings.get(i).code] = (value != null) ? (-value[siblings.get(i).left] - 1) : (-siblings.get(i).left - 1);

                if (value != null && (-value[siblings.get(i).left] - 1) >= 0) {
                    error = -2;
                    return 0;
                }

                progress++;
            } else {
                int h = insert(newSiblings);
                base[begin + siblings.get(i).code] = h;
            }
        }
        return begin;
    }

    public int getSize() {
        return size;
    }


    /**
     * 构建DoubleArrayTrie
     *
     * @param key 所有的词
     * @return
     */
    public int build(List<String> key) {
        keys = new ArrayList<>(key);
        return build(key, null, null, key.size());
    }

    /**
     * 构建DoubleArrayTrie
     *
     * @param wordList 所有的词
     * @param _length
     * @param _value
     * @param wordSize 词数量
     * @return
     */
    public int build(List<String> wordList, int[] _length, int[] _value, int wordSize) {
        if (wordSize > wordList.size() || wordList == null)
            return 0;

        key = wordList;
        length = _length;
        keySize = wordSize;
        value = _value;
        progress = 0;

        resize(65536 * 32);

        base[0] = 1; // root节点base数组对应的值设置为1
        nextCheckPos = 0; // 下一个check的节点

        Node rootNode = new Node();
        rootNode.left = 0;
        rootNode.right = keySize;
        rootNode.depth = 0;

        List<Node> siblings = new ArrayList<>();
        fetch(rootNode, siblings);
        insert(siblings);

        used = null;
        key = null;

        return error;
    }


    public List<Integer> commonPrefixSearch(String key) {

        int len = key.length();
        int nodePos = 0;
        List<Integer> result = new ArrayList<>();

        char[] keyChars = key.toCharArray();

        int b = base[nodePos];
        int n;
        int p;

        int index = 0;
        for (int i = 0; i < len; i++) {
            p = b;
            n = base[p];

            if (b == check[p] && n < 0) {
                index = i - 1;
                result.add(-n - 1);
            }

            p = b + (int) (keyChars[i]) + 1;
            if (b == check[p])
                b = base[p];
            else {
                System.out.println(index);
                return result;
            }
        }

        p = b;
        n = base[p];

        if (b == check[p] && n < 0) {
            index = len;
            result.add(-n - 1);
        }

        System.out.println(len);
        return result;
    }

    public int commonPrefixSearch1(String key, int pos) {

        int len = key.length();
        int nodePos = 0;

        char[] keyChars = key.toCharArray();

        int b = base[nodePos];
        int n;
        int p;

        int index = 0;
        for (int i = pos; i < len; i++) {
            p = b;
            n = base[p];

            if (b == check[p] && n < 0) {
                index = i - 1;
            }

            p = b + (int) (keyChars[i]) + 1;
            if (b == check[p])
                b = base[p];
            else {
                break;
            }
        }

       /* p = b;
        n = base[p];

        if (b == check[p] && n < 0) {
            index = len;
        }*/

        return index;
    }

    public List<String> getAllMatch(String key) {
        List<String> words = new ArrayList<>();
        while (true) {
            if (key.length() == 0) {
                break;
            }

            List<Integer> wordIndex = commonPrefixSearch(key);
            if (wordIndex.size() == 0) {
                key = key.substring(1);
                continue;
            }

            String thisS = "";

            if (wordIndex.size() == 1) {
                thisS = keys.get(wordIndex.get(0));
            } else {
                for (Integer index : wordIndex) {
                    String s = keys.get(index);
                    if (s.length() > thisS.length()) {
                        thisS = s;
                    }
                }
            }
            words.add(thisS);
            key = key.substring(thisS.length());

        }
        return words;
    }

    public List<String> getAllMatch1(String key) {
        List<String> words = new ArrayList<>();


        int i = 0;


        while (true) {
            if (key.length() < i) {
                break;
            }

            int index = commonPrefixSearch1(key, i);
            if (index == 0) {
                i++;
                continue;
            }
            words.add(key.substring(i, i + index + 1));
            i = index + 1;

        }
        return words;
    }


}
